/**
 * Created with IntelliJ IDEA.
 * Description :
 * User: $ {USER}
 * Date: $ {YEAR}-$ {MONTH}一$ { DAY}
 * Time: ${ TIME}
 */

/**
 * 题目：反转链表 II
 * 思路：这个与我们前面做的反转链表题目有些不一样，因为这个是在一个区间内反转，而不是整体反转。
 *      核心思想还是反转链表，我们只需要把区间内链表反转即可。
 *      把要反转的区间断开，自己反转，反转之后就可以进行连接了。
 *      找到要反转的区间的最前一个节点，找到要反转的最后一个节点即可。
 *      注意的是：头节点可能会被反转，因此我们要有一个虚拟节点来当其前一个节点
 */

public class Test {
    public ListNode reverseBetween(ListNode head, int left, int right) {
        // 区间反转链表，找到前驱和后继指针
        if (head.next == null || left == right) {
            return head;
        }
        ListNode newHead = new ListNode(-1, head);
        ListNode cur = newHead;
        int leftlen = 0;
        // 找到left的前一个位置的节点
        while (leftlen < left-1) {
            leftlen++;
            cur = cur.next;
        }
        // 找到right位置的节点
        ListNode leftNode = cur; // 链表的左节点
        while (leftlen < right) {
            leftlen++;
            cur = cur.next;
        }
        ListNode rightNode = cur.next;
        cur.next = null;
        cur = leftNode.next.next;
        ListNode prev = leftNode.next;
        ListNode node = prev;
        // 反转区间链表
        while (cur != null) {
            ListNode curNext = cur.next;
            cur.next = prev;
            prev = cur;
            cur = curNext;
            curNext = curNext == null ? null : curNext.next;
        }
        // 链接链表
        leftNode.next = prev;
        node.next = rightNode;
        return newHead.next;
    }
}

class ListNode {
    int val;
    ListNode next;

    ListNode() {
    }

    ListNode(int val) {
        this.val = val;
    }

    ListNode(int val, ListNode next) {
        this.val = val;
        this.next = next;
    }
}
